package Top_Interview_Questions.Stack;

/**
 * @Author: 吕庆龙
 * @Date: 2020/1/8 16:45
 * <p>
 * 功能描述:
 */


public class _0042 {

    /**
     * 动态规划法
     *
     * 别人的解析
     * https://leetcode-cn.com/problems/trapping-rain-water/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-8/
     *
     * 解析:
     * 1.别人的解析那里,j>=0。没有必要,只需要算到max_right[1]即可。因为后面没用到
     * max_right[0]
     */
    public int trap(int[] height) {
        int sum = 0;
        int length = height.length;
        int[] max_left = new int[length];
        int[] max_right = new int[length];

        for(int i = 1;i < length - 1;i++){
            max_left[i] = Math.max(max_left[i-1],height[i-1]);
        }
        for(int j = length - 2;j >= 1;j--){//1.
            max_right[j] = Math.max(max_right[j+1],height[j+1]);
        }

        int min;
        for (int i = 1;i < height.length - 1;i++){
            min = Math.min(max_left[i],max_right[i]);
            if(min > height[i]){
                sum = sum + (min - height[i]);
            }
        }
        return sum;
    }

}
